package com.ggqq.day315;
//74  https://leetcode-cn.com/problems/search-a-2d-matrix/
public class search2Matrix {
    public static void main(String[] args){
        int[][] matrix ={{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        int target = 3;
        search2Matrix s = new search2Matrix();
    //    System.out.println(s.search(matrix, target));
        System.out.println(s.search1(matrix, target));

    }
    //方法一：暴力
    public boolean search(int[][] matrix,int target){
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                if(matrix[i][j]==target){
                    return true;
                }
            }
        }
        return false;
    }
    //方法二：对第一列进行二分查找
    public boolean search1 (int[][] matrix,int target){
        int left=0;
        int right = matrix.length;
        while(left+1<right){
            int mid =(left+right)/2;
            if(matrix[mid][0]==target){
                return true;
            }else if(matrix[mid][0]>target){
                right=mid;//这里不能写成right = mid-1 会出现right减到0的情况
            }else{
                left=mid;
            }
        }
        //对matrix[mid][0]这行进行遍历
        for(int i= 0;i<matrix[0].length;i++){
            if(matrix[left][i]==target){
                return true;
            }
        }
        return false;

    }

}
